package com.ftg.learn.chapter11.datastruct;


/**
 * 连式单节点
 * 线性存储结构
 * 顺序
 * 链式
 * 队列
 * 栈
 *
 * @author kangjx
 * @version 1.0
 * @date 2023/2/6 下午1:17
 */
public class LinkList<I> {

    /**
     * 什么类型存储结构来完成这个处理
     */
    private final Node<I> head;

    /**
     * 指针指向链尾
     */
    private Node<I> tail;

    private int index;

    /**
     * 中项 ：  如何计算 ...
     *  1  ： 一堆 30分钟 15分钟
     *  2  :  c.getNext.getNext();
     *        d.getNext();
     */

    /**
     * 求有多少个可用元素
     *
     * @return
     */
    public int size() {
        return index;
    }

    /**
     * 通过指定的元素 下标查找当前结点
     *
     * @param index
     * @return
     */
    private Node<I> findNodeByIndex(int index) {
        // 下标
        if (index < 0) {
            throw new RuntimeException(ExceptionTip.IndexLessZero.getMess());
        }
        //插入添加一个容错
        if(head.getNext() == null && index > 0){
            throw new RuntimeException(ExceptionTip.OnlyHaveOneHead.getMess());
        }

        if(index > this.size()){
            throw new RuntimeException(ExceptionTip.OverSize.getMess());
        }

        return getNode(index);
    }

    private Node<I> getNode(int index){
        //删除 时添加一个容错
        Node<I> temp1 = head;
        int no = 0;
        while (null != temp1.getNext() && no != index) {
            temp1 = temp1.getNext();
            no++;
        }
        return temp1;
    }

    public I getVal(int index){
        return findNodeByIndex(index).getVal();
    }

    /**
     * 删除时
     *    长度
     *    val问题
     *    删除的下标超过 总长度时间
     * @param index  下标
     * @return
     */
    public boolean delByIndex(int index) {
        Node<I> currNode = findNodeByIndex(index - 1);
        if(index == size()){
            this.tail = currNode;
        }else{
            currNode.setNext(currNode.getNext().getNext());
        }
        this.index--;
        return true;
    }

    public boolean insertByIndex(int index, I val) {
        //我本身
        Node<I> currNode = findNodeByIndex(index);

        //新节点
        Node<I> newNode = new Node(val);
        newNode.setNext(currNode.getNext());

        currNode.setNext(newNode);

        return true;
    }

    public LinkList() {
        //头节点
        this.head = new Node<I>(null);
        this.tail = this.head;
    }

    /**
     * 追加方法
     * 两指针  一个指向头一个指向尾
     *
     * @param val 实际值
     */
    public void addTail(I val) {
        tail.setNext(new Node<I>(val));
        tail = tail.getNext();
        this.index++;
    }

    /**
     * 向链表的尾添加一个元素
     * 采用的是循环方式 ， 取最后一个元素
     *
     * @param val 元素值
     */
    public void add(I val) {
        //产生临时节点
        Node<I> temp = new Node(val);
        //。。。。
        //思路  找到最后一个getNext为null
        Node<I> temp1 = this.head;
        while (null != temp1.getNext()) {
            temp1 = temp1.getNext();
        }
        temp1.setNext(temp);
        this.index++;
    }

    /**
     * 递归方法
     *
     * @param val love
     */
    public void addRecursive(I val) {
        Node<I> tail = findTail(head);
        tail.setNext(new Node(val));
        this.index++;
    }

    /**
     * 递归  ： 指的一定方法
     * 在方法体当中，有一段代码调用自己
     *
     * @param curr 当前节点  一般head
     * @return 最后一个不为null的node
     */
    public Node<I> findTail(Node<I> curr) {
        Node<I> nextNode = curr.getNext();
        if (null != nextNode) {
            return findTail(nextNode);
        }
        return curr;
    }

    //改递归 ....

    /**
     * 链式存储结构节点
     */
    @SuppressWarnings("all")
    private class Node<I> {
        I val;
        Node next;

        public Node(I val) {
            this.val = val;
        }

        public Node(I val, Node next) {
            this.val = val;
            this.next = next;
        }

        public I getVal() {
            return val;
        }

        public void setVal(I val) {
            this.val = val;
        }

        public Node<I> getNext() {
            return next;
        }

        public void setNext(Node<I> next) {
            this.next = next;
        }
    }

    /**
     * 求中项  为优化快速查询  下标大于中间的元素
     * @param head
     * @return
     */
    public Node<I> middleMyNode(Node<I> head){
        Node<I> fast = head;
        Node<I> slow = head;
        while (null != fast && null != fast.getNext()){
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        }
        return  slow;
    }

}
